FIG. 1 illustrates a bus 3 in a computer (not shown). Processors P1-P4 have access to the bus 3. A memory controller C1 is connected to the bus 3, and controls traffic to, and from, memory M1. Bridges B1-BN are also connected to the bus 3. Each bridge, in effect, acts as an adaptor circuit which allows the bus 3 to communicate with another type of bus (not shown), which can connect to a source or repository of data, such as memory, or a peripheral.
Sometimes a processor P, such as processor P1, will impose a "lock" on the bus 3, by activating lock line L. The lock prevents all other agents, such as the other processors P2-P4, and the bridges B, from gaining access to the bus 3. The lock allows the processor P1 to perform a sequence of operations on memory, without interference by the other processors or the bridges.
As a simple example, processor P1 may (1) impose the lock, (2) read the data stored at memory address X, (3) modify the data read, (4) write the modified data to address X, and (5) release the lock.
If the lock were not imposed in step (1), then, immediately after processor P1 read the data at address X, another processor, such as P2, may read the same data. Then, after the processor P1 replaced the data with the modified data in step (4), the replaced data may be inconsistent with that held by processor P2. A data coherency problem would arise: the data held by processor P2 would not be an accurate copy of data at address X. The lock prevents this problem from occurring.
In a multi-bus system, the situation becomes more complex. FIG. 2 illustrates busses BA, BB, and BC. Processors P1-P4 are connected to bus BA. Processors PS-P8 are connected to bus BC. Bridges B1-BN are connected to bus BB. Controllers C1 and C2 control traffic to, and from, memories M1 and M2, respectively.
One problem which can arise in this system is that a program may run on processor P1 which writes words outside memory M1, such as to memory M2, through bus BC. However, processor P1 has no effective way to issue a lock on bus BC. This inability to lock bus BC can create the data coherency problem described in the Background of the Invention, because another agent can read, or write, data at an address in memory M2 which is being altered by processor P1.
Another problem can arise. Assume that processor P1 issues a lock, and that P1's operations, which follow the lock, involve writing a word through bridge B1, to a memory address on the "other side" 6 of bridge B1.
Assume also that, independent of processor P1's activities, (1) an agent A1 posts a write operation which requires involvement of bridge B1 for completion, and that (2) this write operation involves a data address which processor P1 had previously cached. Consequently, for this posted write operation to proceed, the cached data must be merged with the data posted by the agent, and then returned to memory. Then the posted write operation can proceed.
Now, a deadlock has occurred. Under the rules of operation, once processor P1 has issued the lock, processor P1 must be allowed to finish its intended steps. It cannot be disrupted by the merging operation of the cached data, described immediately above. Thus, the request of agent A1 is blocked.
However, processor P1 needs bridge B1. But, under other rules of operation, bridge B1 has become irrevocably involved in the write operation posted by agent A1. In effect, bridge B1 has become a "one-way street" running in the direction of the write operation of agent A1. This direction is opposite the direction required by processor P1.
P1 has blocked the merging needed by A1, and A1 has blocked the bridge needed by P1. No further action can be taken, and the system has become stalled, or deadlocked.